| 1. Identity statement | |
| Reference Type | Conference Paper (Conference Proceedings) |
| Site | sibgrapi.sid.inpe.br |
| Holder Code | ibi 8JMKD3MGPEW34M/46T9EHH |
| Identifier | 6qtX3pFwXQZG2LgkFdY/UNhNr |
| Repository | sid.inpe.br/sibgrapi@80/2008/07.18.15.09 |
| Last Update | 2008:07.18.15.09.32 (UTC) administrator |
| Metadata Repository | sid.inpe.br/sibgrapi@80/2008/07.18.15.09.34 |
| Metadata Last Update | 2022:06.14.00.13.46 (UTC) administrator |
| DOI | 10.1109/SIBGRAPI.2008.24 |
| Citation Key | AryaFonsMoun:2008:TrApRa |
| Title | Tradeoffs in approximate range searching made simpler  |
| Format | Printed, On-line. |
| Year | 2008 |
| Access Date | 2024, Apr. 28 |
| Number of Files | 1 |
| Size | 207 KiB |
| 2. Context | |
| Author | 1 Arya, Sunil 2 Fonseca, Guilherme D. da 3 Mount, David M. |
| Affiliation | 1 The Hong Kong University of Science and Technology 2 University of Maryland 3 University of Maryland |
| Editor | Jung, Cláudio Rosito Walter, Marcelo |
| Conference Name | Brazilian Symposium on Computer Graphics and Image Processing, 21 (SIBGRAPI) |
| Conference Location | Campo Grande, MS, Brazil |
| Date | 12-15 Oct. 2008 |
| Publisher | IEEE Computer Society |
| Publisher City | Los Alamitos |
| Book Title | Proceedings |
| Tertiary Type | Full Paper |
| History (UTC) | 2008-07-18 15:09:34 :: fonseca@cos.ufrj.br -> administrator :: 2009-08-13 20:38:55 :: administrator -> fonseca@cos.ufrj.br :: 2010-08-28 20:03:22 :: fonseca@cos.ufrj.br -> administrator :: 2022-06-14 00:13:46 :: administrator -> :: 2008 |
| 3. Content and structure | |
| Is the master or a copy? | is the master |
| Content Stage | completed |
| Transferable | 1 |
| Version Type | finaldraft |
| Keywords | range searching geometric approximation geometric data structures computational geometry |
| Abstract | Range searching is a fundamental problem in computational geometry. The problem involves preprocessing a set of n points in R^d into a data structure, so that it is possible to determine the subset of points lying within a given query range. In approximate range searching, a parameter eps > 0 is given, and for a given query range R the points lying within distance eps diam(R) of the range's boundary may be counted or not. In this paper we present three results related to the issue of tradeoffs in approximate range searching. First, we introduce the range sketching problem. Next, we present a space-time tradeoff for smooth convex ranges, which generalize spherical ranges. Finally, we show how to modify the previous data structure to obtain a space-time tradeoff for simplex ranges. In contrast to existing results, which are based on relatively complex data structures, all three of our results are based on simple, practical data structures. |
| Arrangement 1 | urlib.net > SDLA > Fonds > SIBGRAPI 2008 > Tradeoffs in approximate... |
| Arrangement 2 | urlib.net > SDLA > Fonds > Full Index > Tradeoffs in approximate... |
| doc Directory Content | access |
| source Directory Content | there are no files |
| agreement Directory Content | there are no files |
| 4. Conditions of access and use | |
| data URL | http://urlib.net/ibi/6qtX3pFwXQZG2LgkFdY/UNhNr |
| zipped data URL | http://urlib.net/zip/6qtX3pFwXQZG2LgkFdY/UNhNr |
| Language | en |
| Target File | tradeoffs-final.pdf |
| User Group | fonseca@cos.ufrj.br administrator |
| Visibility | shown |
| 5. Allied materials | |
| Mirror Repository | sid.inpe.br/banon/2001/03.30.15.38.24 |
| Next Higher Units | 8JMKD3MGPEW34M/46SG4TH 8JMKD3MGPEW34M/4742MCS |
| Citing Item List | sid.inpe.br/sibgrapi/2022/05.14.04.55 4 |
| Host Collection | sid.inpe.br/banon/2001/03.30.15.38 |
| 6. Notes | |
| Empty Fields | archivingpolicy archivist area callnumber contenttype copyholder copyright creatorhistory descriptionlevel dissemination documentstage e-mailaddress edition electronicmailaddress group isbn issn label lineage mark nextedition notes numberofvolumes orcid organization pages parameterlist parentrepositories previousedition previouslowerunit progress project readergroup readpermission resumeid rightsholder schedulinginformation secondarydate secondarykey secondarymark secondarytype serieseditor session shorttitle sponsor subject tertiarymark type url volume |